home *** CD-ROM | disk | FTP | other *** search
/ Aminet 6 / Aminet 6 - June 1995.iso / Aminet / gfx / 3d / irit50src.lha / irit5 / trim_lib / iso_crvs.c next >
Encoding:
C/C++ Source or Header  |  1995-01-30  |  19.2 KB  |  515 lines
  1. /******************************************************************************
  2. * Iso_Crvs.c - Computes iso parametric curves of trimmed surfaces.          *
  3. *******************************************************************************
  4. * Written by Gershon Elber, Nov. 94.                          *
  5. ******************************************************************************/
  6.  
  7. #include "trim_loc.h"
  8. #include "symb_lib.h"
  9.  
  10. #ifdef DOUBLE
  11. #define ISO_PARAM_PERTURB 1.23456789e-8
  12. #else
  13. #define ISO_PARAM_PERTURB 1.23456789e-4
  14. #endif /* DOUBLE */
  15.  
  16. #define MIN_SIZE_CRV    1e-5
  17.  
  18. typedef struct IsoInterStruct {
  19.     struct IsoInterStruct *Pnext;
  20.     CagdRType Param;
  21. } IsoInterStruct;
  22.  
  23. int _TrimUVSamplesPerCurve = 128;
  24. CagdBType
  25.     _TrimUVSamplesOptimal = FALSE;
  26.  
  27. static CagdCrvStruct *TrimCrvTrimParamList(CagdCrvStruct *Crv,
  28.                        IsoInterStruct *InterList);
  29. static IsoInterStruct **TrimIntersectTrimCrvIsoVals(TrimSrfStruct *TrimSrf,
  30.                             int Dir,
  31.                             CagdRType *OrigIsoParams,
  32.                             int NumOfIsocurves);
  33. static void InsertIntersections(IsoInterStruct **Inters,
  34.                 CagdRType *IsoParams,
  35.                 int Index1,
  36.                 int Index2,
  37.                 CagdRType Val1,
  38.                 CagdRType Val2,
  39.                 CagdRType OVal1,
  40.                 CagdRType OVal2);
  41. static int FindLocationInIsoParams(CagdRType Val,
  42.                    CagdRType *IsoParams,
  43.                    int NumOfIsocurves);
  44.  
  45. /*****************************************************************************
  46. * DESCRIPTION:                                                               M
  47. *   Routine to convert a single trimmed surface to NumOfIsolines polylines   M
  48. * in each parametric direction with SamplesPerCurve in each isoparametric    M
  49. * curve.                                      M
  50. *   Polyline are always E3 of CagdPolylineStruct type.                 M
  51. *   Iso parametric curves are sampled equally spaced in parametric space.    M
  52. *   NULL is returned in case of an error, otherwise list of                  M
  53. * CagdPolylineStruct. Attempt is made to extract isolines along C1           M
  54. * discontinuities first.                             M
  55. *                                                                            *
  56. * PARAMETERS:                                                                M
  57. *   TrimSrf:           To extract isoparametric curves from.                 M
  58. *   NumOfIsocurves:    In each (U or V) direction.                           M
  59. *   SamplesPerCurve:   Fineness control on piecewise linear curve            M
  60. *                      approximation.                                        M
  61. *   Optimal:           Use optimal approximation of isocurves.             M
  62. *                                                                            *
  63. * RETURN VALUE:                                                              M
  64. *   CagdPolylineStruct *: List of polylines representing a piecewise linear  M
  65. *                         approximation of the extracted isoparamteric       M
  66. *                         curves or NULL is case of an error.                M
  67. *                                                                            *
  68. * KEYWORDS:                                                                  M
  69. *   TrimSrf2Polylines, isoparametric curves                                  M
  70. *****************************************************************************/
  71. CagdPolylineStruct *TrimSrf2Polylines(TrimSrfStruct *TrimSrf,
  72.                       int NumOfIsocurves[2],
  73.                       int SamplesPerCurve,
  74.                       int Optimal)
  75. {
  76.     CagdCrvStruct *Crv,
  77.         *Crvs = TrimSrf2Curves(TrimSrf, NumOfIsocurves);
  78.     CagdPolylineStruct *Poly,
  79.     *Polys = NULL;
  80.  
  81.     for (Crv = Crvs; Crv != NULL; Crv = Crv -> Pnext) {
  82.     Poly = SymbCrv2Polyline(Crv, SamplesPerCurve, Optimal, TRUE);
  83.     Poly -> Pnext = Polys;
  84.     Polys = Poly;
  85.     }
  86.  
  87.     CagdCrvFreeList(Crvs);
  88.     return Polys;    
  89. }
  90.  
  91. /*****************************************************************************
  92. * DESCRIPTION:                                                               M
  93. *   Routine to extract from a trimmed surface NumOfIsoline isocurve list     M
  94. * in each param. direction.                             M
  95. *   Iso parametric curves are sampled equally spaced in parametric space.    M
  96. *   NULL is returned in case of an error, otherwise list of CagdCrvStruct.   M
  97. * As the isoparametric curves are trimmed according to the trimming curves   M
  98. * the resulting number of curves is arbitrary.                     M
  99. *                                                                            *
  100. * PARAMETERS:                                                                M
  101. *   TrimSrf:         To extract isoparametric curves from.                   M
  102. *   NumOfIsocurves:  In each (U or V) direction.                             M
  103. *                                                                            *
  104. * RETURN VALUE:                                                              M
  105. *   CagdCrvStruct *:  List of extracted isoparametric curves. These curves   M
  106. *                     inherit the order and continuity of the original Srf.  M
  107. *                     NULL is returned in case of an error.                  M
  108. *                                                                            *
  109. * KEYWORDS:                                                                  M
  110. *   TrimSrf2Curves, curves, isoparametric curves                             M
  111. *****************************************************************************/
  112. CagdCrvStruct *TrimSrf2Curves(TrimSrfStruct *TrimSrf, int NumOfIsocurves[2])
  113. {
  114.     int i, NumC1Disconts,
  115.     ULength = TrimSrf -> Srf -> ULength,
  116.     VLength = TrimSrf -> Srf -> VLength,
  117.     UOrder = TrimSrf -> Srf -> UOrder,
  118.     VOrder = TrimSrf -> Srf -> VOrder;
  119.     CagdRType UMin, UMax, VMin, VMax, *C1Disconts,
  120.     *UIsoParams, *VIsoParams;
  121.     IsoInterStruct **UInters, **VInters;
  122.     CagdCrvStruct *Crv,
  123.     *CrvList = NULL;
  124.  
  125.     /* Make sure requested format is something reasonable. */
  126.     if (NumOfIsocurves[0] < 2)
  127.     NumOfIsocurves[0] = 2;
  128.     if (NumOfIsocurves[1] <= 0)
  129.     NumOfIsocurves[1] = NumOfIsocurves[0];
  130.     else if (NumOfIsocurves[1] < 2)
  131.     NumOfIsocurves[1] = 2;
  132.  
  133.     TrimSrfDomain(TrimSrf, &UMin, &UMax, &VMin, &VMax);
  134.  
  135.     if (CAGD_IS_BSPLINE_SRF(TrimSrf -> Srf)) {
  136.     /* Compute discontinuities along u axis and use that to determine    */
  137.     /* where to extract isolines along u.                     */
  138.     /* Note C1Disconts is freed by BspKnotParamValues.             */
  139.     C1Disconts = BspKnotAllC1Discont(TrimSrf -> Srf -> UKnotVector, UOrder,
  140.                      ULength, &NumC1Disconts);
  141.     UIsoParams = BspKnotParamValues(UMin, UMax, NumOfIsocurves[0],
  142.                     C1Disconts, NumC1Disconts);
  143.  
  144.  
  145.     /* Compute discontinuities along v axis and use that to determine    */
  146.     /* where to extract isolines along v.                     */
  147.     /* Note C1Disconts is freed by BspKnotParamValues.             */
  148.     C1Disconts = BspKnotAllC1Discont(TrimSrf -> Srf -> VKnotVector, VOrder,
  149.                      VLength, &NumC1Disconts);
  150.     VIsoParams = BspKnotParamValues(VMin, VMax, NumOfIsocurves[1],
  151.                     C1Disconts, NumC1Disconts);
  152.     }
  153.     else if (CAGD_IS_BEZIER_SRF(TrimSrf -> Srf)) {
  154.     UIsoParams = (CagdRType *) IritMalloc(sizeof(RealType) *
  155.                             NumOfIsocurves[0]);
  156.     for (i = 0; i < NumOfIsocurves[0]; i++)
  157.         UIsoParams[i] = ((CagdRType) i) / (NumOfIsocurves[0] - 1);
  158.  
  159.     VIsoParams = (CagdRType *) IritMalloc(sizeof(RealType) *
  160.                             NumOfIsocurves[1]);
  161.     for (i = 0; i < NumOfIsocurves[1]; i++)
  162.         VIsoParams[i] = ((CagdRType) i) / (NumOfIsocurves[1] - 1);
  163.     }
  164.     else {
  165.     TRIM_FATAL_ERROR(TRIM_ERR_BZR_BSP_EXPECT);
  166.     return NULL;
  167.     }
  168.  
  169.     UInters = TrimIntersectTrimCrvIsoVals(TrimSrf, CAGD_CONST_U_DIR,
  170.                       UIsoParams, NumOfIsocurves[0]);
  171.     VInters = TrimIntersectTrimCrvIsoVals(TrimSrf, CAGD_CONST_V_DIR,
  172.                       VIsoParams, NumOfIsocurves[1]);
  173.  
  174.     for (i = 0; i < NumOfIsocurves[0]; i++) {
  175.     CagdCrvStruct *Crvs, *CrvsLast;
  176.  
  177.     Crv = CagdCrvFromSrf(TrimSrf -> Srf, UIsoParams[i],
  178.                  CAGD_CONST_U_DIR);
  179.     /* Both Crv and UInters[i] are freed by TrimCrvTrimParamList: */
  180.     if ((Crvs = TrimCrvTrimParamList(Crv, UInters[i])) != NULL) {
  181.         CrvsLast = (CagdCrvStruct *) CagdListLast(Crvs);
  182.         CrvsLast -> Pnext = CrvList;
  183.         CrvList = Crvs;
  184.     }
  185.     }
  186.  
  187.     for (i = 0; i < NumOfIsocurves[1]; i++) {
  188.     CagdCrvStruct *Crvs, *CrvsLast;
  189.  
  190.     Crv = CagdCrvFromSrf(TrimSrf -> Srf, VIsoParams[i],
  191.                  CAGD_CONST_V_DIR);
  192.     /* Both Crv and UInters[i] are freed by TrimCrvTrimParamList: */
  193.     if ((Crvs = TrimCrvTrimParamList(Crv, VInters[i])) != NULL) {
  194.         CrvsLast = (CagdCrvStruct *) CagdListLast(Crvs);
  195.         CrvsLast -> Pnext = CrvList;
  196.         CrvList = Crvs;
  197.     }
  198.     }
  199.  
  200.     IritFree((VoidPtr) UInters);
  201.     IritFree((VoidPtr) VInters);
  202.     IritFree((VoidPtr) UIsoParams);
  203.     IritFree((VoidPtr) VIsoParams);
  204.  
  205.     return CrvList;
  206. }
  207.  
  208. /*****************************************************************************
  209. * DESCRIPTION:                                                               *
  210. *   Trim Crv at the domains prescribed in the intersection list InterList    *
  211. * Both Crv and InterList are freed in this routine.                 *
  212. *                                                                            *
  213. * PARAMETERS:                                                                *
  214. *   Crv:         To trim out according to the prescribed intersections.      *
  215. *   InterList:   List of intersections, as parameters into Crv.              *
  216. *                                                                            *
  217. * RETURN VALUE:                                                              *
  218. *   CagdCrvStruct *:  List of trimmed curves. May be empty (NULL).           *
  219. *****************************************************************************/
  220. static CagdCrvStruct *TrimCrvTrimParamList(CagdCrvStruct *Crv,
  221.                        IsoInterStruct *InterList)
  222. {
  223.     CagdCrvStruct
  224.     *CrvList = NULL;
  225.  
  226.     while (InterList != NULL) {
  227.     if (InterList -> Pnext == NULL) {
  228.         TRIM_FATAL_ERROR(TRIM_ERR_ODD_NUM_OF_INTER);
  229.         return NULL;
  230.     }
  231.     else {
  232.         IsoInterStruct
  233.         *InterNext = InterList -> Pnext -> Pnext;
  234.         CagdRType
  235.             T1 = InterList -> Param,
  236.         T2 = InterList -> Pnext -> Param;
  237.  
  238.         if (T2 - T1 > MIN_SIZE_CRV) {
  239.         CagdCrvStruct
  240.             *TCrv = CagdCrvRegionFromCrv(Crv, T1, T2);
  241.  
  242.         LIST_PUSH(TCrv, CrvList);
  243.         }
  244.  
  245.         IritFree((VoidPtr) InterList -> Pnext);
  246.         IritFree((VoidPtr) InterList);
  247.         InterList = InterNext;
  248.     }
  249.     }
  250.  
  251.     CagdCrvFree(Crv);
  252.  
  253.     return CrvList;
  254. }
  255.  
  256. /*****************************************************************************
  257. * DESCRIPTION:                                                               *
  258. *   Computes the intersections of the trimming curves of TrimSrf with the    *
  259. * ordered isoparametric values prescribed by IspParams, in axis Axis.        *
  260. *                                                                            *
  261. * PARAMETERS:                                                                *
  262. *   TrimSrf:        Trimmed surface to consider.                             *
  263. *   Dir:            Either U or V.                                 *
  264. *   OrigIsoParams:  Vectors of isoparametric values in direction Dir.        *
  265. *   NumOfIsocurves: Size of vector IsoParams.                                *
  266. *                                                                            *
  267. * RETURN VALUE:                                                              *
  268. *   IsoInterStruct **:   A vector of size NumOfIsocurves, each contains a    *
  269. *          list of intersection parameter values.             *
  270. *****************************************************************************/
  271. static IsoInterStruct **TrimIntersectTrimCrvIsoVals(TrimSrfStruct *TrimSrf,
  272.                             int Dir,
  273.                             CagdRType *OrigIsoParams,
  274.                             int NumOfIsocurves)
  275. {
  276.     int i, Axis, OAxis;
  277.     IsoInterStruct
  278.     **Inters = (IsoInterStruct **)
  279.             IritMalloc(sizeof(IsoInterStruct *) * NumOfIsocurves);
  280.     TrimCrvStruct
  281.     *TrimCrv = TrimSrf -> TrimCrvList;
  282.     CagdRType
  283.     *IsoParams = (CagdRType *) IritMalloc(sizeof(RealType) *
  284.                                   NumOfIsocurves);
  285.  
  286.     for (i = 0; i < NumOfIsocurves; i++) {
  287.     Inters[i] = NULL;
  288.  
  289.     IsoParams[i] = OrigIsoParams[i] +
  290.         ISO_PARAM_PERTURB * (i / ((CagdRType) NumOfIsocurves) - 0.51);
  291.     }
  292.  
  293.     for( ; TrimCrv != NULL; TrimCrv = TrimCrv -> Pnext) {
  294.     TrimCrvSegStruct
  295.         *TrimCrvSeg = TrimCrv -> TrimCrvSegList;
  296.  
  297.     switch (Dir) {
  298.         case CAGD_CONST_U_DIR:
  299.             Axis = 1;
  300.         OAxis = 2;
  301.         break;
  302.         case CAGD_CONST_V_DIR:
  303.         Axis = 2;
  304.         OAxis = 1;
  305.         break;
  306.         default:
  307.         TRIM_FATAL_ERROR(TRIM_ERR_DIR_NOT_CONST_UV);
  308.         return NULL;
  309.     }
  310.  
  311.     for ( ; TrimCrvSeg != NULL; TrimCrvSeg = TrimCrvSeg -> Pnext) {
  312.         int UVSize, Index1, Index2;
  313.         CagdCrvStruct
  314.         *UVCrv = TrimCrvSeg -> UVCrv;
  315.  
  316.         if (UVCrv -> Order > 2) {
  317.         CagdPolylineStruct
  318.             *UVPoly = SymbCrv2Polyline(UVCrv, _TrimUVSamplesPerCurve,
  319.                            _TrimUVSamplesOptimal, TRUE);
  320.  
  321.         UVSize = UVPoly -> Length;
  322.  
  323.         Axis--;              /* XYZ is counted from zero, not one. */
  324.         OAxis--;
  325.  
  326.         Index1 = FindLocationInIsoParams(UVPoly ->
  327.                              Polyline[0].Pt[Axis],
  328.                          IsoParams, NumOfIsocurves);
  329.         for (i = 1; i < UVSize; i++) {
  330.             Index2 = FindLocationInIsoParams(UVPoly ->
  331.                               Polyline[i].Pt[Axis],
  332.                              IsoParams,
  333.                              NumOfIsocurves);
  334.             if (Index1 != Index2) {
  335.             InsertIntersections(Inters, IsoParams, Index1, Index2,
  336.                         UVPoly -> Polyline[i-1].Pt[Axis],
  337.                         UVPoly -> Polyline[i].Pt[Axis],
  338.                         UVPoly -> Polyline[i-1].Pt[OAxis],
  339.                         UVPoly -> Polyline[i].Pt[OAxis]);
  340.             }
  341.             Index1 = Index2;
  342.         }
  343.  
  344.         CagdPolylineFree(UVPoly);
  345.         }
  346.         else {
  347.         CagdRType
  348.             **Points = UVCrv -> Points;
  349.  
  350.         UVSize = UVCrv -> Length;
  351.  
  352.         Index1 = FindLocationInIsoParams(Points[Axis][0],
  353.                          IsoParams,
  354.                          NumOfIsocurves);
  355.         for (i = 1; i < UVSize; i++) {
  356.             Index2 = FindLocationInIsoParams(Points[Axis][i],
  357.                              IsoParams,
  358.                              NumOfIsocurves);
  359.             if (Index1 != Index2) {
  360.             InsertIntersections(Inters, IsoParams, Index1, Index2,
  361.                         Points[Axis][i-1],
  362.                         Points[Axis][i],
  363.                         Points[OAxis][i-1],
  364.                         Points[OAxis][i]);
  365.  
  366.             }
  367.             Index1 = Index2;
  368.         }
  369.         }
  370.     }
  371.     }
  372.  
  373.     IritFree((VoidPtr) IsoParams);
  374.  
  375.     return Inters;
  376. }
  377.  
  378. /*****************************************************************************
  379. * DESCRIPTION:                                                               *
  380. *   Updates the intersection vector of lists Inters with the linear segment  *
  381. * of the trimming curves from (Val1, OVal1) to (Val2, OVal2) affecting       *
  382. * indices from Index1 to Index2 in IsoParams.                     *
  383. *                                                                            *
  384. * PARAMETERS:                                                                *
  385. *   Inters:     Vector of intersections with isoparameter values.            *
  386. *   IsoParams:  Vectors isoparameter values.                                 *
  387. *   Index1:    Index of first coordinate of intersection into IsoParams.    *
  388. *   Index2:    Index of second coordinate of intersection into IsoParams.   *
  389. *   Val1:       Parameter value of first intersection.                       *
  390. *   Val2:       Parameter value of second intersection.                      *
  391. *   OVal1:      Other parameter value of first intersection.                 *
  392. *   OVal2:      Other parameter value of second intersection.                *
  393. *                                                                            *
  394. * RETURN VALUE:                                                              *
  395. *   void                                                                     *
  396. *****************************************************************************/
  397. static void InsertIntersections(IsoInterStruct **Inters,
  398.                 CagdRType *IsoParams,
  399.                 int Index1,
  400.                 int Index2,
  401.                 CagdRType Val1,
  402.                 CagdRType Val2,
  403.                 CagdRType OVal1,
  404.                 CagdRType OVal2)
  405. {
  406.     int i;
  407.  
  408.     if (Index1 > Index2)
  409.     SWAP(int, Index1, Index2);
  410.  
  411.     for (i = Index1; i <= Index2; i++) {
  412.     IsoInterStruct *Inter;
  413.     CagdRType
  414.         t = (Val1 - IsoParams[i]) / (Val1 - Val2);
  415.  
  416.     if (t < 0.0 || t > 1.0)
  417.         continue;
  418.  
  419.     Inter = (IsoInterStruct *) IritMalloc(sizeof(IsoInterStruct));
  420.     Inter -> Param = OVal1 * (1.0 - t) + OVal2 * t;
  421.     Inter -> Pnext = NULL;
  422.  
  423.     /* Insert into the vector of intersection lists. */
  424.     if (Inters[i] == NULL)
  425.         Inters[i] = Inter;
  426.     else if (Inters[i] -> Param > Inter -> Param) {
  427.         Inter -> Pnext = Inters[i];
  428.         Inters[i] = Inter;
  429.     }
  430.     else {
  431.         IsoInterStruct *InterTmp;
  432.  
  433.         for (InterTmp = Inters[i];
  434.          InterTmp -> Pnext != NULL;
  435.          InterTmp = InterTmp -> Pnext) {
  436.         if (InterTmp -> Pnext -> Param > Inter -> Param)
  437.             break;
  438.         }
  439.  
  440.         if (InterTmp -> Pnext == NULL)
  441.         InterTmp -> Pnext = Inter;
  442.         else {
  443.         Inter -> Pnext = InterTmp -> Pnext;
  444.         InterTmp -> Pnext = Inter;
  445.         }
  446.     }
  447.     }
  448. }
  449.  
  450. /*****************************************************************************
  451. * DESCRIPTION:                                                               *
  452. *   Finds the index in IsoParams, that is the maximal value that is less     *
  453. * than or equal to Val.                                                      *
  454. *                                                                            *
  455. * PARAMETERS:                                                                *
  456. *   Val:          Real value to search in vector.                            *
  457. *   IsoParams:    Vectors of isoparametric values in direction Dir.          *
  458. *   NumOfIsocurves:   Size of vector IsoParams.                              *
  459. *                                                                            *
  460. * RETURN VALUE:                                                              *
  461. *   int:          Found index.                                               *
  462. *****************************************************************************/
  463. static int FindLocationInIsoParams(CagdRType Val,
  464.                    CagdRType *IsoParams,
  465.                    int NumOfIsocurves)
  466. {
  467.     int MidIndex,
  468.     MinIndex = 0,
  469.     MaxIndex = NumOfIsocurves - 1;
  470.  
  471.     while (MaxIndex - MinIndex >= 2) {
  472.     MidIndex = (MinIndex + MaxIndex) / 2;
  473.  
  474.     if (IsoParams[MidIndex] <= Val)
  475.         MinIndex = MidIndex;
  476.     else
  477.         MaxIndex = MidIndex;
  478.     }
  479.  
  480.     if (IsoParams[MinIndex + 1] <= Val)
  481.     return MinIndex + 1;
  482.     else if (IsoParams[MinIndex] <= Val)
  483.     return MinIndex;
  484.     else
  485.         return -1;
  486. }
  487.  
  488. /*****************************************************************************
  489. * DESCRIPTION:                                                               M
  490. *   Sets the tolerances to use when approximating higher order trimming      M
  491. * curves using piecewise linear approximation, for intersection computation. M
  492. *                                                                            *
  493. * PARAMETERS:                                                                M
  494. *   UVSamplesPerCurve:  Piecewise linear approximation of high order         M
  495. *            trimming curves - number of samples per curve.         M
  496. *   UVSamplesOptimal:   Do we want optimal sampling (see CagdCrv2Polyline).  M
  497. *                                                                            *
  498. * RETURN VALUE:                                                              M
  499. *   int:  Old number of samples per curve.                                   M
  500. *                                                                            *
  501. * KEYWORDS:                                                                  M
  502. *   TrimSetTrimCrvLinearApprox                                               M
  503. *****************************************************************************/
  504. int TrimSetTrimCrvLinearApprox(int UVSamplesPerCurve,
  505.                    int UVSamplesOptimal)
  506. {
  507.     int OldSamplesPerCurve = _TrimUVSamplesPerCurve;
  508.  
  509.     _TrimUVSamplesPerCurve = UVSamplesPerCurve,
  510.     _TrimUVSamplesOptimal = UVSamplesOptimal;
  511.  
  512.     return OldSamplesPerCurve;
  513. }
  514.  
  515.